/*
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

 

示例 1：

输入：n = 12
输出：21
示例 2：

输入：n = 21
输出：-1
 

提示：

1 <= n <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

/*
把 n 转换成字符串（字符数组），那么本题实际上是在求字符数组的 31. 下一个排列，当不存在下一个排列时返回 −1。

4,5,2,6,3,1
左边较小数：2
右边较大数：3

4 5 3 6 2 1
4 5 3 1 2 6

*/
class Solution {
public:
    int nextGreaterElement(int n) {
        string nums = to_string(n);
        int len = nums.length();
        // 从右往左找到第一个递减的数。即左边较小数
        int i = len - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i < 0) {
            return -1;
        }
        // 从右往左找到第一个大于nums[i]的数。即右边较大数
        int j = len - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            --j;
        }
        // 交换i和j的数字
        swap(nums[i], nums[j]);
        // 重排左边较小数后面的序列
        reverse(nums.begin() + i + 1, nums.end());
        long res = stol(nums);
        return res > INT_MAX ? -1 : res;
    }
};

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        return (next_permutation(s.begin(), s.end()) && stol(s) <= INT_MAX) ? stoi(s) : -1;
    }
};
